package ACM_Brush;

public class Solution208 {
    public static void main(String[] args) {
        Trie root = new Trie();
        root.insert("apple");
        System.out.println(root.search("apple"));
        ;
        System.out.println(root.search("app"));
        ;
        System.out.println(root.startWith("app"));
        ;
        root.insert("app");
        System.out.println(root.search("app"));
        ;
    }
}

class Trie {

    Trie[] chids = new Trie[26]; // 26 个子节点
    boolean isLeaf = false; // 当前节点是否为叶子节点

    public void insert(String s) {
        Trie node = this;
        for (char c : s.toCharArray()) {
            if (node.chids[c - 'a'] == null)
                node.chids[c - 'a'] = new Trie();
            node = node.chids[c - 'a'];
        }
        node.isLeaf = true;
    }

    public boolean startWith(String s) {
        Trie node = this;
        for (char c : s.toCharArray()) {
            if (node.chids[c - 'a'] == null)
                return false;
            node = node.chids[c - 'a'];
        }
        return true;
    }

    public boolean search(String s) {
        Trie node = this;
        for (char c : s.toCharArray()) {
            if (node.chids[c - 'a'] == null)
                return false;
            node = node.chids[c - 'a'];
        }
        return node.isLeaf;
    }

}
